package cn.my.quickSort;

import java.util.Arrays;

public class QuickSort {
	public void sort(int[] a, int left, int right){
		if (left > right){
			return;
		}
		int i = left;
		int j = right;
		int partition = a[i];
		while (i < j){
			while (i<j && a[j]>=partition){
				j--;
			}
			if (i < j){
				a[i++] = a[j];
			}
			while (i<j && a[i]<partition){
				i++;
			}
			if (i < j){
				a[j--] = a[i];
			}
		}
		a[i] = partition;
		sort(a, left, i-1);
		sort(a, i+1, right);
	}
	public void quickSort(int[] a){	
		sort(a, 0, a.length-1);
	}
	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		int a[] = {49, 79, 56, 38, 40, 84};
		qs.quickSort(a);
		System.out.println(Arrays.toString(a));
	}
}
